#include <vector>

using namespace std;

void InsertSort(vector<int> &array)
{
    for(int i = 1; i < array.size(); i++)
    {
        int end = i - 1, tmp = array[i];
        while(end >= 0)
        {
            if(tmp < array[end])
            {
                array[end + 1] = array[end];
                end--;
            }
            else break;
        }
        array[end + 1] = tmp;
    }
    
}